package org.aplombh.java.awcing.basic.struct.queue;

import java.util.Scanner;

/**
 * 给定一个大小为 n≤106 的数组。
 *
 * 有一个大小为 k 的滑动窗口，它从数组的最左边移动到最右边。
 *
 * 你只能在窗口中看到 k 个数字。
 *
 * 每次滑动窗口向右移动一个位置。
 *
 * 以下是一个例子：
 *
 * 该数组为 [1 3 -1 -3 5 3 6 7]，k 为 3。
 *
 * 窗口位置	最小值	最大值
 * [1 3 -1] -3 5 3 6 7	-1	3
 * 1 [3 -1 -3] 5 3 6 7	-3	3
 * 1 3 [-1 -3 5] 3 6 7	-3	5
 * 1 3 -1 [-3 5 3] 6 7	-3	5
 * 1 3 -1 -3 [5 3 6] 7	3	6
 * 1 3 -1 -3 5 [3 6 7]	3	7
 * 你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。
 *
 * 输入格式
 * 输入包含两行。
 *
 * 第一行包含两个整数 n 和 k，分别代表数组长度和滑动窗口的长度。
 *
 * 第二行有 n 个整数，代表数组的具体数值。
 *
 * 同行数据之间用空格隔开。
 *
 * 输出格式
 * 输出包含两个。
 *
 * 第一行输出，从左至右，每个位置滑动窗口中的最小值。
 *
 * 第二行输出，从左至右，每个位置滑动窗口中的最大值。
 *
 * 输入样例：
 * 8 3
 * 1 3 -1 -3 5 3 6 7
 * 输出样例：
 * -1 -3 -3 -3 3 3
 * 3 3 5 5 6 7
 */
public class SlidingWindow_154 {
    private static final int N = 1000001;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        //Storing raw arrays
        //存储原数组
        int[] a = new int[N];

        // 单调队列，存储当前存储滑动窗口中每个值的下标
        int[] stack = new int[N];

        int n = scanner.nextInt();
        int k = scanner.nextInt();

        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }

        int head = 0, tail = -1;

        // Use monotone stacks to ensure that each popup and push is a minimum or maximum
        // 利用单调栈，保证每次弹出和加入的都是最小值或最大值
        for (int i = 0; i < n; i++) {
            // Determine whether the sliding window size is exceeded，Stack [head] stores the first index of the current sliding window
            // 判断是否超出滑动窗口大小，stack[head]存储当前滑动窗口的第一个下标, 左端点位置加窗口大小不能越界
            if (head <= tail && stack[head] < i - k + 1) head++;

            // Pops anything larger than the current number on the stack
            // 将栈中比当前数大的都弹出, 保证每次添加都是递增
            while (head <= tail && a[stack[tail]] >= a[i]) tail--;

            // push the stack
            // 加入栈
            stack[++tail] = i;

            // Filter the first few cases that are smaller than the window size
            // 过滤前几次小于窗口大小的情况
            if (i >= k - 1) System.out.print(a[stack[head]] + " ");

        }

        // idem
        // 同上
        System.out.println();
        head = 0;
        tail = -1;
        for (int i = 0; i < n; i++) {
            if (head <= tail && stack[head] < i - k + 1) head++;

            while (head <= tail && a[stack[tail]] <= a[i]) tail--;

            stack[++tail] = i;
            if (i >= k - 1) System.out.print(a[stack[head]] + " ");
        }

    }
}
